# -*- coding: utf-8 -*-

#-------------------------------------------------------------------------------
# Name:        sudoku_solver
# Purpose:
#
# Author:      Alexey
#
# Created:     22.02.2014
# Copyright:   (c) Alexey Zakharenkov 2014
# Licence:     <your licence>
#-------------------------------------------------------------------------------

# How many boxes (call squares/rectangles) along X and Y axes
BOXES_X = 3
BOXES_Y = 3

# Box dimensions
BOX_WIDTH = 3
BOX_HEIGHT = 3

# Maximum digit value
MAX_DIGIT = ((BOX_WIDTH)*(BOX_HEIGHT))

# Field dimensions
WIDTH  = ((BOXES_X)*(BOX_WIDTH ))
HEIGHT = ((BOXES_Y)*(BOX_HEIGHT))

USE_DIAGONALS = False # TODO: make this a command-line parameter

assert WIDTH == HEIGHT and WIDTH == MAX_DIGIT, "Width does not equal Height"


def read(filename):
    """Red sudoku puzzle from a file"""
    field = []
    with open(filename, 'r') as f:
        linesCnt = 0
        while linesCnt < HEIGHT:
            line = f.readline()
            line = line.strip()
            if line:
                linesCnt += 1
                field.append([int(x) for x in line.split()])
    return field


def printField(field):
    for row in field:
        print (' '.join(str(n) for n in row))


def can_digit_stand(field, row, col, digit):
    """Can the digit occupy the cell (row, col)"""
    if field[row][col] != 0:
        return False # cell is already occupied

    # check row
    for r in range(HEIGHT):
        if field[r][col] == digit:
            return False

    # check column
    for c in range(WIDTH):
        if field[row][c] == digit:
            return False

    # check box
    # (R,C) - left upper corner of the box
    R = row // BOX_HEIGHT * BOX_HEIGHT
    C = col // BOX_WIDTH * BOX_WIDTH;

    for r in range(BOX_HEIGHT):
        for c in range(BOX_WIDTH):
            if field[R+r][C+c] == digit:
                return False

    if USE_DIAGONALS:
        # check main diagonal (row == column)
        if row == col:
            for i in range(WIDTH):
                if i != col and field[i][i] == digit:
                    return False
        # check secondary diagonal (row + col == WIDTH-1)
        if row == WIDTH - 1 - col:
            for c in range(WIDTH):
                if c != col and field[WIDTH - 1 - c][c] == digit:
                    return False

    return True


def try_only_possible_digit_in_cell(field, row, col):
    """Returns the only digit that can occupy the cell (row, col), or None"""
    happy_digit = None
    digits_cnt = 0

    if field[row][col]:
        return None

    for digit in range(1, MAX_DIGIT + 1):
        if can_digit_stand(field, row, col, digit):
            happy_digit = digit
            digits_cnt += 1
            if digits_cnt > 1:
                return None

    if digits_cnt == 1:
       field[row][col] = happy_digit
       return {'digit': happy_digit, 'row': row, 'column': col}


def try_only_possible_digit_in_row(field, row):
    """Maybe some digits can stand only at one place at the row"""
    for digit in range(1, MAX_DIGIT + 1):
        possible_places_cnt = 0

        for col in range(WIDTH):
            if can_digit_stand(field, row, col, digit):
                happy_col = col
                possible_places_cnt += 1
                if possible_places_cnt > 1:
                    break

        if possible_places_cnt == 1:
            field[row][happy_col] = digit
            return {'digit': digit, 'column': happy_col, 'row': row}
    return None


def try_only_possible_digit_in_column(field, col):
    """Maybe some digits can stand only at one place at the column"""
    for digit in range(1, MAX_DIGIT + 1):
        possible_places_cnt = 0

        for row in range(HEIGHT):
            if can_digit_stand(field, row, col, digit):
                happy_row = row;
                possible_places_cnt += 1
                if possible_places_cnt > 1:
                    break

        if possible_places_cnt == 1:
            field[happy_row][col] = digit
            return {'digit': digit, 'row': happy_row, 'column': col}

    return None


def try_only_possible_digit_on_main_diagonal(field):
    """Maybe some digits can stand only at one place on the main diagonal"""
    for digit in range(1, MAX_DIGIT + 1):
        possible_places_cnt = 0

        for row in range(HEIGHT):
            col = row # on main diagonal col == row
            if can_digit_stand(field, row, col, digit):
                happy_row = row
                happy_col = col
                possible_places_cnt += 1
                if possible_places_cnt > 1:
                    break
        if possible_places_cnt == 1:
            field[happy_row][happy_col] = digit
            return {'digit': digit, 'row': happy_row, 'column': happy_col}

    return None


def try_only_possible_digit_on_secondary_diagonal(field):
    """Maybe some digits can stand only at one place on the secondary diagonal"""
    for digit in range(1, MAX_DIGIT + 1):
        possible_places_cnt = 0

        for row in range(HEIGHT):
            col = WIDTH - 1 - row # on secondary diagonal col + row == WIDTH - 1
            if can_digit_stand(field, row, col, digit):
                happy_row = row
                happy_col = col
                possible_places_cnt += 1
                if possible_places_cnt > 1:
                    break
        if possible_places_cnt == 1:
            field[happy_row][happy_col] = digit
            return {'digit': digit, 'row': happy_row, 'column': happy_col}

    return None


def try_only_possible_digit_in_box(field, R, C):
    """Maybe some digits can stand only at one place at the box (R,C)"""
    for digit in range(1, MAX_DIGIT):
        possible_places_cnt = 0

        for row in range(R* BOX_HEIGHT, (R+1)*BOX_HEIGHT):
            for col in range(C*BOX_WIDTH, (C+1)*BOX_WIDTH):
                if can_digit_stand(field, row, col, digit):
                    happy_row = row
                    happy_column = col
                    possible_places_cnt += 1
                    if possible_places_cnt > 1:
                        break

        if possible_places_cnt == 1:
            field[happy_row][happy_column] = digit
            return {'digit': digit, 'row': happy_row, 'column': happy_column}

    return None


def improve(field):
    """Put one next digit and returns a dictionary with keys 'digit', 'row', 'column', или None"""
    for R in range(BOXES_Y):
        for C in range(BOXES_X):
            result = try_only_possible_digit_in_box(field, R, C)
            if result:
                return result

    for row in range(HEIGHT):
        result = try_only_possible_digit_in_row(field, row)
        if result:
            return result

    for col in range(WIDTH):
        result = try_only_possible_digit_in_column(field, col)
        if result:
            return result


    if USE_DIAGONALS:
        result = try_only_possible_digit_on_main_diagonal(field)
        if result:
            return result

        result = try_only_possible_digit_on_secondary_diagonal(field)
        if result:
            return result

    for row in range(HEIGHT):
        for col in range(WIDTH):
            result = try_only_possible_digit_in_cell(field, row, col)
            if result:
                return result

    return None


def is_solved(field):
    for row in range(HEIGHT):
        for col in range(WIDTH):
            if field[row][col] == 0:
                return False
    return True



def main():
    field = read("input.txt")

    current_improves = None
    total_improves = 0

    while True:
        is_impoved = improve(field)
        if is_impoved:
            total_improves += 1
        else:
            break

    print("is solved = %d" % int(is_solved(field)))
    print("improves = %d\n" % total_improves)
    printField(field)


if __name__ == '__main__':
    main()


